package com.leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class L0112 {

    public static void main(String[] args) {
        Integer []nums={5,4,8,11,null,13,4,7,2,null,null,null,1};
        TreeNode root=new L0112().createTree(nums);
        new L0112().hasPathSum(root,23);
    }
    public TreeNode createTree(Integer []nums){
        TreeNode root=null;
        TreeNode point;
        Queue<TreeNode> queue = new LinkedList<>();
        if(nums.length>=1){
            root=new TreeNode(nums[0]);
            queue.add(root);
        }
        int i=1;
        while (i<nums.length){
            point=queue.poll();
            if(null!=nums[i]){
                point.left=new TreeNode(nums[i]);
                queue.add(point.left);
            }
            i++;
            if(i>=nums.length){
                break;
            }
            if(null!=nums[i]){
                point.right=new TreeNode(nums[i]);
                queue.add(point.right);
            }
            i++;
        }
        return root;
    }
    public void printTree(TreeNode treeNode,String str){
        if(null==treeNode){
            return;
        }else{
            printTree(treeNode.left,str+"**");
            System.out.println(str+treeNode.val);
            printTree(treeNode.right,str+"**");
        }
    }
    public void hasPathSum(TreeNode root, int targetSum) {
//            if (root==null)
//                return false;
            pathSum(root,targetSum,0);
    }

    public void pathSum(TreeNode root,int target,int sum){
         if (sum+root.val==target)
             System.out.println(sum+ root.val);
         if (root.left!=null){
              pathSum(root.left,target,sum+root.val);
         }
         if (root.right!=null){
              pathSum(root.right,target,sum+root.val);
         }
    }
//    public boolean hasPathSum(TreeNode root, int sum) {
//        if (root == null) {
//            return false;
//        }
//        if (root.left == null && root.right == null) {
//            return sum == root.val;
//        }
//        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
//    }
}
